package heap;

public class LeftistHeap<T extends  Comparable<T>> {

    private LeftistNode<T> mRoot;

        public void print() {
            if (mRoot != null)
                print(mRoot, mRoot.data, 0);
        }


    private class LeftistNode<T extends Comparable<T>>{
        T data;
        int npl;
        LeftistNode<T> left;
        LeftistNode<T> right;

        public LeftistNode(T data, LeftistNode<T> left, LeftistNode<T> right) {
            this.data = data;
            this.npl = 0;
            this.left = left;
            this.right = right;
        }

        @Override
        public String toString() {
            return "LeftistNode{" +
                    "data=" + data +
                    '}';
        }
    }

    public LeftistHeap(){
        mRoot = null;
    }

    private void preOrder(LeftistNode<T> heap){
        if(heap!=null){
            System.out.println(heap.data+" ");
            preOrder(heap.left);
            preOrder(heap.right);
        }
    }

    public void preOrder(){
        preOrder(mRoot);
    }

    private void inOrder(LeftistNode<T> heap){
        if(heap!=null){
            inOrder(heap.left);
            System.out.println(heap.data+" ");
            inOrder(heap.right);
        }
    }

    public void inOrder(){
        inOrder(mRoot);
    }

    private void postOrder(LeftistNode<T> heap){
        if(heap!=null){
            postOrder(heap.left);
            postOrder(heap.right);
            System.out.println(heap.data+" ");
        }
    }

    public void postOrder(){
        postOrder(mRoot);
    }

    /**合并左倾堆x和左倾堆y
     * @param x
     * @param y
     * @return
     */
    private LeftistNode<T> merge(LeftistNode<T> x,LeftistNode<T> y){
        if(x == null)return y;
        if(y == null)return x;
        //合并X和Y时，将X作为合并后的树的根
        //这里的操作保证X的根小于Y的根
        //交换X和Y
        if(x.data.compareTo(y.data)>0){
            LeftistNode<T> tmp = x;
            x = y;
            y = tmp;
        }

        x.right = merge(x.right,y);

        //如果 X的左孩子为空 或者X的左孩子的npl小于右孩子，则交换x和Y
        if(x.left == null || x.left.npl<x.right.npl){
            LeftistNode<T> tmp = x.left;
            x.left = x.right;
            x.right = tmp;
        }

        if(x.right == null || x.left == null)
            x.npl = 0;
        else
            x.npl = (x.left.npl>x.right.npl)?(x.right.npl+1):(x.left.npl+1);

        return x;

    }

    public void merge(LeftistHeap<T> other){
        this.mRoot = merge(this.mRoot,other.mRoot);
    }

    /** 新建结点，并将其插入到左倾堆中
     * @param data
     */
    public void insert(T data){
        LeftistNode<T> node = new LeftistNode<T>(data,null,null);
        if(node!=null)
            this.mRoot = merge(this.mRoot,node);
    }

    public T remove(){
        if(this.mRoot == null)
            return null;
        T data = this.mRoot.data;
        LeftistNode<T> l = this.mRoot.left;
        LeftistNode<T> r = this.mRoot.right;

        this.mRoot = null;
        this.mRoot = merge(l,r);
        return data;
    }

    private void destory(LeftistNode<T> heap){
        if(heap==null)
            return;
        if(heap.left!=null){
            destory(heap.left);
        }

        if(heap.right!=null){
            destory(heap.right);
        }
    }

    public void clear(){
        destory(mRoot);
        mRoot = null;
    }

    public void print(LeftistNode<T> heap,T data,int direction){
        if(heap!=null){
            if(direction == 0)
                System.out.printf("%2d(%d) is root\n",heap.data,heap.npl);
            else
                System.out.printf("%2d(%d) is %2d's %6s child\n", heap.data, heap.npl, data, direction==1?"right" : "left");
            print(heap.left,heap.data,-1);
            print(heap.right,heap.data,1);
        }
    }

}
